package com.liuwei.spring.cloud.junit.leetcode.substring;

import com.alibaba.fastjson2.JSON;
import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.cn/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150
 */
@Slf4j
public class TextJustification {

    /**
     * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本
     * 文本的最后一行应为左对齐，且单词之间不插入额外的空格
     * @param args
     */
    public static void main(String[] args) {
        TextJustification instance = new TextJustification();
        String[] text = {"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"};
        int maxWidth = 20;
        log.info("average :{}", 5/2);
        List<String> result = instance.fullJustify(text, maxWidth);
        log.info("result :{}", JSON.toJSONString(result));
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int i = 0;
        int j = 0;
        Map<Integer,Integer> lengths = new HashMap<Integer,Integer>();
        while (i < words.length) {
            String word = words[j];
            lengths.put(j,word.length());
            int sum = sumLength(i,j,lengths);
            if (sum > maxWidth) {
                String value = addResult(words,i,j-1,maxWidth,false);
                result.add(value);
                i=j;
            }else{
                j++;
                if(j>=words.length){
                    String value = addResult(words,i,j-1,maxWidth,true);
                    result.add(value);
                    break;
                }
            }
        }
        return result;
    }

    private int sumLength(int start,int end,Map<Integer,Integer> lengths){
        int sum = 0;
        for (int i = start; i <=end ; i++) {
            sum = sum + lengths.get(i);
        }
        return sum+end-start;
    }

    private String addResult(String[] words,int start,int end,int width,boolean isEnd){
        StringBuilder sb = new StringBuilder();
        for (int i = start; i <=end ; i++) {
            sb.append(words[i]);
            sb.append(" ");
        }
        String value = sb.toString().trim();
        int len = value.length();
        int wordsSpace = end - start;
        int toAdd = width-len;
        if(toAdd==0 || wordsSpace==0){
            //do nothing
            return value;
        }else{
            StringBuilder nsb = new StringBuilder();
            if(isEnd){
                nsb.append(value);
                for (int i = 0; i < toAdd; i++) {
                    nsb.append(" ");
                }
                return nsb.toString().trim();
            }
            int average = toAdd%wordsSpace==0?toAdd/wordsSpace:toAdd/wordsSpace+1;
            int last = toAdd - (wordsSpace-1)*average;
            for (int i = start; i <=end ; i++) {
                nsb.append(words[i]);
                nsb.append(" ");
                if(i==end-1){
                    for (int j = 0; j < last; j++) {
                        nsb.append(" ");
                    }
                    continue;
                }
                for (int j = 0; j < average; j++) {
                    nsb.append(" ");
                }
            }
            return nsb.toString().trim();
        }
    }
}
